package Tree;
/*
顺序二叉树通常只考虑完全二叉树
第n个元素的左子节点为2 * n+1
第n个元素的右子节点为2* n+ 2
第n个元素的父节点为(n-1)/2
注：n从0开始
 */
public class ArrBinaryTreeDemo {

  public static void main(String[] args) {
    /*
       1
    2    3
  4  5  6  7
  前：1 2 4 5 3 6 7
  中：4 2 5 1 6 3 7
  后：4 5 2 6 7 3 1
     */
    int[]arr = new int[]{1,2,3,4,5,6,7};
//    测试
    ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
    System.out.print("前序遍历：");
    arrBinaryTree.preOrder(0);
    System.out.println();
    System.out.print("中序遍历：");
    arrBinaryTree.infixOrder(0);
    System.out.println();
    System.out.print("后序遍历：");
    arrBinaryTree.postOrder(0);
  }
}
//顺序存储的二叉排序树
class ArrBinaryTree{
  private int[]arr;

  public ArrBinaryTree(int[] arr) {
    this.arr = arr;
  }

  public void preOrder(int index){
    if (arr == null || arr.length == 0){
      System.out.println("二叉树为空，无法前序遍历");
    }
    System.out.print(arr[index] + " ");
//    向左递归
    if ((2 * index + 1 ) < arr.length){//确保下标不会越界
      preOrder(2 * index + 1);
    }
//    向右递归
    if ((2 * index + 2 ) < arr.length){//确保下标不会越界
      preOrder(2 * index + 2);
    }
  }
  public void infixOrder(int index){
    if (arr == null || arr.length == 0){
      System.out.println("二叉树为空，无法前序遍历");
    }
//    向左递归
    if ((2 * index + 1 ) < arr.length){//确保下标不会越界
      infixOrder(2 * index + 1);
    }
    System.out.print(arr[index] + " ");
//    向右递归
    if ((2 * index + 2 ) < arr.length){//确保下标不会越界
      infixOrder(2 * index + 2);
    }
  }
  public void postOrder(int index){
    if (arr == null || arr.length == 0){
      System.out.println("二叉树为空，无法前序遍历");
    }
//    向左递归
    if ((2 * index + 1 ) < arr.length){//确保下标不会越界
      postOrder(2 * index + 1);
    }
//    向右递归
    if ((2 * index + 2 ) < arr.length){//确保下标不会越界
      postOrder(2 * index + 2);
    }
    System.out.print(arr[index] + " ");
  }
}
